package backtrack.passed;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author xyyi
 * 
 * 
 *         Given a 2D board containing 'X' and 'O', capture all regions
 *         surrounded by 'X'.
 * 
 *         A region is captured by flipping all 'O's into 'X's in that
 *         surrounded region .
 * 
 *         For example, X X X X X O O X X X O X X O X X After running your
 *         function, the board should be:
 * 
 *         X X X X X X X X X X X X X O X X
 */

public class SurroundedRegions {

	/*
	 * DFS
	 */
	public void solve(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0) {
			return;
		}

		int rows = board.length;
		int cols = board[0].length;

		for (int col = 0; col < rows; col++) {
			dfs(board, 0, col);
			dfs(board, rows - 1, col);
		}

		for (int row = 1; row < rows - 1; row++) {
			dfs(board, row, 0);
			dfs(board, row, cols - 1);
		}

		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] == 'O') {
					board[row][col] = 'X';
				} else if (board[row][col] == 'D') {
					board[row][col] = 'O';
				}
			}
		}
	}

	private void dfs(char[][] board, int row, int col) {
		int rows = board.length;
		int cols = board[0].length;

		if (row < 0 || row >= rows || col < 0 || col >= cols
		        || board[row][col] != 'O')
			return;

		board[row][col] = 'D';
		dfs(board, row - 1, col);
		dfs(board, row, col + 1);
		dfs(board, row + 1, col);
		dfs(board, row, col - 1);
	}

	/*
	 * BFS
	 */
	public void solveBFS(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0) {
			return;
		}

		int rows = board.length;
		int cols = board[0].length;

		for (int col = 0; col < rows; col++) {
			bfs(board, 0, col);
			bfs(board, rows - 1, col);
		}

		for (int row = 1; row < rows - 1; row++) {
			bfs(board, row, 0);
			bfs(board, row, cols - 1);
		}

		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] == 'O') {
					board[row][col] = 'X';
				} else if (board[row][col] == 'D') {
					board[row][col] = 'O';
				}
			}
		}
	}

	private void bfs(char[][] board, int row, int col) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int rows = board.length;
		fill(board, row, col, queue);

		while (!queue.isEmpty()) {
			int n = queue.poll();
			int r = n / rows;
			int c = n % rows;

			fill(board, r - 1, c, queue);
			fill(board, r, c + 1, queue);
			fill(board, r + 1, c, queue);
			fill(board, r, c - 1, queue);
		}

	}

	private void fill(char[][] board, int row, int col, Queue<Integer> queue) {
		int rows = board.length;
		int cols = board[0].length;
		if (row < 0 || row >= rows || col < 0 || col >= cols
		        || board[row][col] != 'O')
			return;
		queue.offer(row * rows + col);
		board[row][col] = 'D';
	}

	/*
	 * Disjoint Set
	 */
	public void solveDS(char[][] board) {
		if (board == null || board.length == 0)
			return;
		int rows = board.length, cols = board[0].length;
		Map<Integer, Integer> ds = new HashMap<Integer, Integer>();
		init(board, ds);
		int outside = getKey(board, rows + 1, cols + 1);
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] == 'X')
					continue;
				if (row == 0 || row == rows - 1 || col == 0 || col == cols - 1) {
					union(getKey(board, row, col), outside, ds);
					continue;
				}

				if (board[row - 1][col] == 'O')
					union(getKey(board, row - 1, col), getKey(board, row, col),
					        ds);
				if (board[row + 1][col] == 'O')
					union(getKey(board, row + 1, col), getKey(board, row, col),
					        ds);
				if (board[row][col - 1] == 'O')
					union(getKey(board, row, col - 1), getKey(board, row, col),
					        ds);
				if (board[row][col + 1] == 'O')
					union(getKey(board, row, col + 1), getKey(board, row, col),
					        ds);
			}
		}

		for (int row = 1; row < rows - 1; row++) {
			for (int col = 1; col < cols - 1; col++) {
				if (board[row][col] == 'O'
				        && find(getKey(board, row, col), ds) != find(outside,
				                ds)) {
					board[row][col] = 'X';
				}
			}
		}

	}

	private int getKey(char[][] board, int row, int col) {
		return row * board.length + col;
	}

	private void init(char[][] board, Map<Integer, Integer> ds) {
		int rows = board.length, cols = board[0].length;
		for (int row = 0; row <= rows + 1; row++) {
			for (int col = 0; col <= cols + 1; col++) {
				int value = getKey(board, row, col);
				ds.put(value, value);
			}
		}
	}

	private int find(int id, Map<Integer, Integer> ds) {
		if (ds.get(id).intValue() == id)
			return id;
		else {
			int result = find(ds.get(id), ds);
			ds.put(id, result);
			return result;
		}
	}

	private void union(int id1, int id2, Map<Integer, Integer> ds) {
		id1 = find(id1, ds);
		id2 = find(id2, ds);
		if (id1 < id2)
			ds.put(id2, id1);
		else
			ds.put(id1, id2);
	}

	/*
	 * Disjoint Set http://collabedit.com/dycyk
	 * 
	 * 
	 * #define I(x,y) ((x) * 1000 + (y)) int ds[1000*1000];
	 * 
	 * int Find(int id) { if (ds[id] != id) return ds[id] = Find(ds[id]); return
	 * id; }
	 * 
	 * 
	 * void Union(int id1, int id2) { id1 = Find(id1); id2 = Find(id2); if (id1
	 * < id2) ds[id2] = id1; else ds[id1] = id2; }
	 * 
	 * 
	 * void Init(int size) { for (int i = 0; i < size; i++) ds[i] = i; }
	 * 
	 * 
	 * void OOXX(vector<vector<char> >& board, int w, int h) { int outside =
	 * I(w+1, h+1); Init(outside+1); for (int i = 0; i < h; i++) { for (int j =
	 * 0; j < w; j++) { if (board[i][j] == 'X') { continue; } if (i == 0 || j ==
	 * 0 || i == h-1 || j == w-1) { Union(I(i,j), outside); continue; } if
	 * (board[i-1][j] == 'O') Union(I(i,j), I(i-1,j)); if (board[i+1][j] == 'O')
	 * Union(I(i,j), I(i+1,j)); if (board[i][j-1] == 'O') Union(I(i,j),
	 * I(i,j-1)); if (board[i][j+1] == 'O') Union(I(i,j), I(i,j+1)); } } for
	 * (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (board[i][j]
	 * == 'O' && Find(I(i,j)) != Find(outside)) { board[i][j] = 'X'; } } } }
	 * 
	 * 
	 * class Solution { public: void solve(vector<vector<char>> &board) { //
	 * Start typing your C/C++ solution below // DO NOT write int main()
	 * function int h = board.size(); if (h==0) return; OOXX(board, h, h); } };
	 */

	public SurroundedRegions() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SurroundedRegions sr = new SurroundedRegions();
		char[][] board = { { 'O', 'O', 'O' }, { 'O', 'O', 'O' },
		        { 'O', 'O', 'O' } };
		board[0][0] = 'O';
		sr.solveDS(board);
	}
}
